The present invention relates to data communications networks and more particularly to a method and system for queue management in networks employing pause time based flow control.
When data processing systems first began to be used commercially on a widespread basis, the standard system configuration was an autonomous mainframe or host computer which could be accessed only through locally-attached terminals. Few people, at that time, perceived any significant benefit from interconnecting host computers.
Over time, it came to be understood that significant commercial advantages could be gained by interconnecting or networking host computers. Data originating with users at one host computer could readily and rapidly be shared with users located at other host computers, even where those other host computers were many miles away. Also, the functional capabilities of a given host computer could be treated as a resource that could be shared not only among locally-attached users but also among remote, network-attached users. Mainframe networks of this type came to be generically referred to as Wide Area Networks, commonly abbreviated to WANs.
Certain parallels existed between the development of mainframe computer technology and the later development of personal computer technology. Early personal computers were relatively unsophisticated devices intended for use by a single user in a stand-alone configuration. Eventually, the same kinds of needs (data sharing and resource sharing) that drove the development of mainframe networks began to drive the development of networks of personal computers and auxiliary devices, such as printers and data storage devices.
While mainframe networks developed primarily using point-to-point connections among widely separated mainframes, personal computer networks developed using a shared or common transmission media to interconnect personal computers and auxiliary devices within a geographically-limited area, such as a building or even an area within the building. Networks of this type came to be generically referred to as Local Area Networks or LANs.
Different LAN technologies exist. Currently the most popular LAN technology is ethernet technology. In an ethernet LAN, personal computers and auxiliary devices share a common bi-directional data bus. In the following description, LAN-attached devices will be generically referred to as stations or LANs stations. Any transmission-capable LAN station may initiate transmission on the bus and every transmission propagates in both directions and is received by every LAN station attached to the same bus, including the transmitting station.
Another popular LAN technology is token ring technology. In a token ring LAN, LAN stations are connected in a logical ring. A station having data to send on the ring looks for a special frame known as a token. When the station receives the token, it writes the data onto the logical ring. The data propagates around the ring through each successive LAN station. If a LAN station receiving the data is the intended destination, that station copies the data into station memory but passes the data onto the next station on the ring. The data continues around the ring until it returns to the transmitting station, which strips the data from the ring but writes the token back onto the ring for use by another station having data to send.
The same user needs (data sharing and resource sharing) which drove the development of LANs have driven the creation of networks consisting of multiple LANs interconnected through boundary devices known as LAN bridges or switches. Point-to-point connections or links between LAN switches permit traffic originating in any given LAN to be transported to a LAN station connected to any other LAN in the same switched network. The given switch-to-switch link typically carries traffic from multiple sources concurrently. Although local area networks, such as ethernet and token ring networks, were originally developed as shared-media LAN technologies, xe2x80x9cswitchedxe2x80x9d technologies are being developed to support full point-to-point duplex links among individual LANs.
In a switched LAN network, multiple stations may decide they want to send data at substantially the same time. If the multiple stations are all on the same LAN, the LAN technology includes a mechanism for avoiding xe2x80x9ccollisionsxe2x80x9d among the multiple stations. As noted earlier, token ring LANs use a token to control transmission. The first station to acquire the token gains access to the ring to the exclusion of other stations who may also had data to send.
In ethernet LANs, a Collision Sense Multiple Access/Carrier Detect (CSMA/CD) protocol is used to resolve conflicts among contending users. When the station has data to transmit, it xe2x80x9clistensxe2x80x9d to the bus to see if the bus is already carrying data from another station. If the bus is found not to be in use, the listening station begins its own transmission immediately. If the bus is found to be in use, the station with data to send waits for a predetermined interval before restarting the bus acquisition process. Since electrical signals require time to propagate down any conductor, two or more stations can listen, find the bus quiet at the time, and begin transmitting simultaneously. If that happens, data from the transmitting stations collide and becomes corrupted. If the transmitting station doesn""t detect the same data transmitted, that station sends a shortjamming signal and stops transmitting. The jamming signal increases the chances that all other transmitting stations will detect the collision and stop transmitting themselves. Following a random delay, each transmitting station restarts the bus acquisition process.
The noted protocols, while fairly effective within single LANs, are ineffective in controlling flow in switched LAN networks since the traffic on any particular link in a switched network usually represents an aggregation of traffic originating at multiple source stations, each of which has legitimately acquired the right to write data onto the shared media of its own local LAN. To provide flow control in switched LAN networks, standards groups such as the Institute of Electrical and Electronic Engineers (IEEE) and the International Telecommunications Union (ITU) have defined link-level flow control protocols. If a system or node in a switched network determines that a link is beginning to supply more traffic than the node can accommodate, the node can start a flow control operation which will reduce the amount of traffic being received at the node over the link in question before the link causes the node to become congested. Whether a node is considered congested is usually determined by whether buffer memories (buffers) at the node have become filled beyond a predetermined threshold, expressed usually as a percentage of maximum buffer capacity. The goal of any flow control mechanism is to avoid a situation in which a node""s buffer has become fully loaded, leaving the node no choice but to discard arriving packets.
In the following discussion, the terms xe2x80x9cupstreamxe2x80x9d and xe2x80x9cdownstreamxe2x80x9d will be used frequently. These terms are used to define the direction of the data flow relative to a particular node or station. Any station or link which supplies data to a given node is considered to be xe2x80x9cupstreamxe2x80x9d of the given node. Any station or link to which the given node sends data is considered to be xe2x80x9cdownstreamxe2x80x9d of the given node.
Under at least one known standard, a node that wants to limit the amount of data received over an upstream link generates a pause frame which contains, among other things, a pause time. Pause times are usually expressed as a number of time slots, with a time slot being the time required to transmit a sixty-four byte packet on the link. When a pause frame is received at the intended upstream station, the station will temporarily suspend transmission of any further traffic over the link for the pause time specified in the pause frame. The pause time gives the affected node time to recover by emptying its buffers of at least some of the excess traffic it has been receiving.
A problem with link-level flow control is that every station supplying traffic to the link is affected whether or not that station is a source of the congestion-inducing traffic or is actually performing within expected parameters. To avoid penalizing well-behaving traffic sources, proposals have been made to extend the concept of link-level flow control down to a station level. According to these proposals, stations that are actually contributing to congestion or near-congestion would be identified by downstream nodes and would be sent pause frames to cause only the misbehaving stations to temporarily suspend or pause sending of traffic for the pause time specified in the pause frames. Traffic source stations that behave within expected parameters would not be affected by flow control messages directed to misbehaving source stations.
The various proposals for station-level flow control have focused on the conditions under which flow control messages are generated or how a downstream node can schedule multiple pause frames to be sent to upstream stations to distribute those pause times over a control period rather than have all pause times start and stop at nearly the same times. The proposals have not focused on the fact that an upstream station may receive multiple pause frames from different downstream nodes and that those pause frames may be inconsistent with each other; that is, may instruct the same upstream station to pause for different, overlapping periods of time.
The present invention is a queue or flow management technique which deals specifically with problems created when a source of data traffic in a network receives inconsistent pause frames from multiple downstream stations or nodes.
In one embodiment of the invention is a method to implement and a network element which operates either in a transmit state or a paused state. The operational state of the network element is controlled in accordance with flow control messages received from destination elements. Each of the flow control messages includes, among other things, a pause time. The network element which receives the flow control message determines whether the network element is already in the paused state when the message is received. If the network element is not in the paused state, it is set into that state and a counter is triggered. The counter times out after the pause time specified in the flow control message. If the network element is already in the paused state and if recently received flow control messages came from the same destination element, the counter is reset or rewritten using the pause time in the most recent flow control message. Otherwise, the counter is set to that pause time only if the pause time is greater than the time remaining in the current pause interval. The network element is returned to the transmit state when the counter finally times out.